package mergeSort;

/**
 *  归并排序的代码实现：
 *  排序3-》01：30：00 讲解
 *  时间复杂度：O(n * log n)
 *  空间复杂度：O(n)
 *  稳定性：稳定的排序 ---> 直接插入  冒泡  归并
 */

public class MyMergeSort {

    //归并排序的具体代码实现：递归实现
    private static void mergeSortRecursion(int[] array,int left,int right) {
        if(left >= right) { return; }

        int mid = (left + right) / 2;
        //1.分解左边
        mergeSortRecursion(array,left,mid);
        //2 .分解右边
        mergeSortRecursion(array,mid+1,right);

        //合并
        merge(array,left,right,mid);

    }
    //合并函数
    private static void merge(int[] array,int start,int end,int midIndex) {
        int[] tmpElem = new int[end-start+1];
        int k = 0;

        int s1 = start;
        int s2 = midIndex+1;

        //两个归并段不为空
        while(s1 <= midIndex && s2 <= end) {
            //array[s1] <= array[s2] ：有等号是稳定的排序
            if(array[s1] <= array[s2]) {
                tmpElem[k++] = array[s1++];
            }else {
                tmpElem[k++] = array[s2++];
            }
        }

        //走到这时有一个归并段没有数据，拷贝另一个段的所有数据到新数组中
        while (s1 <= midIndex) {
            tmpElem[k++] = array[s1++];
        }
        while (s2 <= end) {
            tmpElem[k++] = array[s2++];
        }
        //把排好序的数字拷贝回原来的数组
        for (int i = 0; i < k; i++) {
            array[i+start] = tmpElem[i];
        }

    }
    public static void mergeSort(int[] array) {
        //mergeSortRecursion(array,0, array.length-1); //递归
        mergeSortNotRecursion(array,0, array.length - 1);  //非递归
    }

    /**
     *  归并排序的非递归实现
     *  02:24:00 讲解
     */
    public static void mergeSortNotRecursion(int[] array,int left,int right) {
        int gap = 1; //每次分组的数据

        while(gap < array.length) {
            for (int i = 0; i < array.length; i += gap*2) {
                //进入循环,i 一定合法
                int e1 = i + gap - 1;
                //防止e1越界
                if(e1 >= array.length) {
                    e1 = array.length - 1;
                }

                int s2 = e1 + 1;
                if(s2 >= array.length) {
                    s2 = array.length - 1;
                }

                int e2 = s2 + gap - 1;
                if(e2 >= array.length) {
                    e2 = array.length - 1;
                }

                //归并
                merge(array,i,e2,e1);
            }
            gap *= 2;
        }
    }
}
